<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
二叉搜索树（BST）是二叉树的一种
只允许你再左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值
基本方法有：
1. 插入节点
2. 删除节点
3. 查找最小值
4. 查找最大值
5. 搜索某个节点
6. 前序遍历
7. 中序遍历
8. 后序遍历
<script>
	{
		const compareUtil = {
			less: -1,
      bigger: 1,
      equal: 0,
			compare (val1, val2) {
				if (val1 === val2) return this.equal
				if (val1 < val2) return this.less
				if (val1 > val2) return this.bigger
      }
    }

		class Node {
			constructor (val) {
				this.value = val
        this.left = null
        this.right = null
			}
    }

		class BST {
			root = null

			// 1. 插入节点
      insert (val) {
        if (!this.root) {
					this.root = new Node(val)
        } else {
					this._insertNode(this.root, val)
        }
      }
			_insertNode (node, val) {
				if (compareUtil.compare(val, node.value) === compareUtil.less) {
					if (node.left) {
						this._insertNode(node.left, val)
          } else {
						node.left = new Node(val)
          }
        } else {
					if (node.right) {
						this._insertNode(node.right, val)
          } else {
						node.right = new Node(val)
          }
        }
      }
			// 2. 删除节点
      remove (val) {
				if (this.root) {
					this._removeNode(this.root, val)
        }
      }
			_removeNode (node, val) {
				if (!node) return null
				if (compareUtil.compare(val, node.value) === compareUtil.less) {
					node.left = this._removeNode(node.left, val)
          return node
        } else if (compareUtil.compare(val, node.value) === compareUtil.bigger) {
					node.right = this._removeNode(node.right, val)
          return node
        } else {
					if (!node.left && !node.right) {
						return null
          }
					if (!node.left) {
						node = node.right
            return node
          }
					if (!node.right) {
						node = node.left
            return node
          }

					let rightMixNode = this._getMin(node.right)
          while (rightMixNode.value === val) {
						node.right = this._removeNode(node.right, val)
	          rightMixNode = this._getMin(node.right)
          }
          node.value = rightMixNode.value
					node.right = this._removeNode(node.right, rightMixNode.value)
          return node
        }
      }
			// 3. 查找最小值
      min () {
				if (!this.root) return false
				let current = this.root
	      current = this._getMin(current)
        return current.value
      }
      _getMin (node) {
        while (node.left) {
	        node = node.left
        }
				return node
      }
			// 4. 查找最大值
      max () {
	      if (!this.root) return false
	      let current = this.root
	      current = this._getMax(current)
        return current.value
      }
			_getMax (node) {
				while (node.right) {
					node = node.right
        }
				return node
      }
			// 5. 搜索某个节点
      search (val) {
				return this._searchNode(this.root, val)
      }
			_searchNode (node, val) {
				if (!node) return false
				if (compareUtil.compare(val, node.value) === compareUtil.less) {
					return this._searchNode(node.left, val)
        } else if (compareUtil.compare(val, node.value) === compareUtil.bigger) {
					return this._searchNode(node.right, val)
        } else {
					return true
        }
      }
			// 6. 前序遍历
      preOrderMap (cb) {
				const inner = (node) => {
					if (!node) return
          cb(node)
          inner(node.left)
          inner(node.right)
        }
				inner(this.root)
      }
			// 7. 中序遍历
      midOrderMap (cb) {
	      const inner = (node) => {
		      if (!node) return
		      inner(node.left)
		      cb(node)
		      inner(node.right)
	      }
	      inner(this.root)
      }
			// 8. 后序遍历
      postOrderMap (cb) {
	      const inner = (node) => {
		      if (!node) return
		      inner(node.left)
		      inner(node.right)
		      cb(node)
	      }
	      inner(this.root)
      }
    }

		const bst = new BST()

		bst.insert(5)
		bst.insert(2)
		bst.insert(7)
		bst.insert(6)
		bst.insert(10)
		bst.insert(7)
		bst.insert(11)

    // bst.remove(7)
    console.log(bst)
    // bst.midOrderMap((node) => {
		// 	console.log(node.value)
    // })
		console.log(bst.search(12))
  }
</script>

<script>
  const compareObj = {
    less: -1,
    bigger: 1,
    equal: 0
  }

  class Node {
    constructor(key) {
      this.key = key
      this.left = null
      this.right = null
    }
  }

  class BST {
    constructor() {
      this.root = null
    }

    insert (key) {
      if (!this.root) {
        this.root = new Node(key)
      } else {
        this.insertNode(this.root, key)
      }
    }

    insertNode (node, key) {
      if (this.compare(key, node.key) === compareObj.less) {
        if (!node.left) {
          node.left = new Node(key)
        } else {
          this.insertNode(node.left, key)
        }
      } else {
        if (!node.right) {
          node.right = new Node(key)
        } else {
          this.insertNode(node.right, key)
        }
      }
    }

    compare (key1, key2) {
      if (key1 === key2) {
        return compareObj.equal
      } else if (key1 < key2) {
        return compareObj.less
      } else {
        return compareObj.bigger
      }
    }

    // 中序遍历（左 根 右）
    inOrderMap (cb) {
      const inner = (node) => {
        if (!node) return
        inner(node.left)
        cb(node.key)
        inner(node.right)
      }

      inner(this.root)
    }

    // 先序遍历（根 左 右）
    preOrderMap (cb) {
      const inner = (node) => {
        if (!node) return
        cb(node.key)
        inner(node.left)
        inner(node.right)
      }

      inner(this.root)
    }

    // 后序遍历（左 右 根）
    postOrderMap (cb) {
      const inner = (node) => {
        if (!node) return
        inner(node.left)
        inner(node.right)
        cb(node.key)
      }

      inner(this.root)
    }

    // 找最小值
    min () {
      let current = this.root
      current = this.getMin(current)
      return current.key
    }

    getMin (node) {
      while (node.left) {
        node = node.left
      }
      return node
    }

    // 找最大值
    max () {
      let current = this.root
      current = this.getMax(current)
      return current.key
    }

    getMax (node) {
      while (node.right) {
        node = node.right
      }
      return node
    }

    // 搜索
    search (key) {
      const inner = (node) => {
        if (!node) return false

        if (this.compare(key, node.key) === compareObj.less) {
          return inner(node.left)
        } else if (this.compare(key, node.key) === compareObj.bigger) {
          return inner(node.right)
        } else {
          return true
        }
      }

      return inner(this.root)
    }

    // 删除
    remove (key) {
      this.root = this.removeNode(this.root, key)
    }

    removeNode (node, key) {
      if (!node) return null

      if (this.compare(key, node.key) === compareObj.less) {
        node.left = this.removeNode(node.left, key)
        return node
      } else if (this.compare(key, node.key) === compareObj.bigger) {
        node.right = this.removeNode(node.right, key)
        return node
      } else {
        if (!node.left && !node.right) {
          node = null
          return node
        }
        if (!node.left) {
          node = node.right
          return node
        } else if (!node.right) {
          node = node.left
          return node
        }

        const target = this.getMin(node.right)
        node.key = target.key
        node.right = this.removeNode(node.right, target.key)
        return node

        /* 下面这段逻辑是删除重复的key */
        // let target = this.getMin(node.right)
        // while (target.key === key) {
        //   node.right = this.removeNode(node.right, target.key)
        //   target = this.getMin(node.right)
        // }
        // node.key = target.key
        // node.right = this.removeNode(node.right, target.key)
        // return node
      }
    }
  }

  const bst = new BST()

  bst.insert(5)
  bst.insert(2)
  bst.insert(6)
  bst.insert(7)
  bst.insert(1)
  bst.insert(3)
  bst.insert(8)
  bst.insert(7)
  bst.insert(20)
  bst.insert(8)
  bst.insert(10)
  bst.insert(9)
  bst.insert(4)

  // bst.postOrderMap((k) => {
  //   console.log(k)
  // })

  // console.log(bst.min())
  // console.log(bst.max())

  // console.log(bst.search(1))
</script>
</body>
</html>
